package datastruct.linkedlist;

import java.util.Objects;
import java.util.function.Consumer;

/**
 * 循环链表
 */
public class CircularLinkedList<T> {

    private Node<T> first;
    private Node<T> last;

    private static class Node<T> {
        T data;
        Node<T> next;
    }

    public CircularLinkedList(T... datas) {
        Node<T> cur = null;
        for (T data : datas) {
            Node<T> node = new Node<>();
            node.data = data;
            if (Objects.nonNull(cur)) {
                // 连接
                node.next = cur.next;
                cur.next = node;
                cur = node;
            } else {
                // 第一个成环
                node.next = node;
                cur = first = node;
            }
            // 当前最后1个
            last = cur;
        }
    }

    /**
     * 遍历
     */
    public void forEach(Consumer<T> consumer) {
        Objects.requireNonNull(consumer);
        if (Objects.isNull(first)) {
            return;
        }
        Node<T> cur = first;
        do {
            consumer.accept(cur.data);
            cur = cur.next;
        } while (cur != first);
    }

    /**
     * 约瑟夫出队
     *
     * @param step  步长
     * @param consumer  出队元素的消费行为
     */
    public void popJosephus(int step, Consumer<T> consumer) {
        Objects.requireNonNull(consumer);
        if (step < 1) {
            throw new RuntimeException("步长[step]不能为空");
        }
        Node<T> cur = last;
        // 开始出队(找到要出队的前一个才能删除)
        --step;
        int count = 0;
        while (cur.next != cur) {
            if (count == step) {
                // 出列元素
                Node<T> node = cur.next;
                consumer.accept(node.data);
                // 连接下一个
                cur.next = node.next;
                // 删除
                node.next = null;
                node.data = null;
                // 步数置0
                count = 0;
            } else {
                cur = cur.next;
                ++count;
            }
        }
        System.out.println("剩下的最后1个元素：" + cur.data);
    }

    /**
     * 全部出队
     *
     * @param step  步长
     * @param consumer  出队元素的消费行为
     */
    public void popAll(int step, Consumer<T> consumer) {
        Objects.requireNonNull(consumer);
        if (step < 1) {
            throw new RuntimeException("步长[step]不能为空");
        }
        Node<T> cur = last;
        // 开始出队(找到要出队的前一个才能删除)
        --step;
        int count = 0;
        while (cur.next != null) {
            if (count == step) {
                // 出列元素
                Node<T> node = cur.next;
                consumer.accept(node.data);
                // 连接下一个
                cur.next = node.next;
                // 删除
                node.next = null;
                node.data = null;
                // 步数置0
                count = 0;
            } else {
                cur = cur.next;
                ++count;
            }
        }
    }
}
